package 数据结构.章节09;

import java.util.Stack;

/**
 * @author 挚爱之夕
 * @date 2021/10/12 - 10 - 12 - 20:33
 * @Description: 数据结构.章节09
 * @Version: 1.0
 */
public class _158_判断回文链表 {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 3, 2, 1};
        Node head = new Node(a[0]);
        Node p = head;
        for (int i = 1; i < a.length; i++) {
            p.next = new Node(a[i]);
            p = p.next;
        }
        p = head;
        while (p != null) {
            System.out.print(p.val + "\t");
            p = p.next;
        }
        System.out.println();
        System.out.println("Is the list palindromic?");
        System.out.println(isPalindrome(head));
    }

    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    private static boolean isPalindrome(Node head) {
        if (head == null)
            return false;
        if (head.next == null)
            return true;
        Node fast = head;
        Node slow = head;
        boolean isOdd = true;
        Stack<Node> stack = new Stack<>();
        while (fast != null && fast.next != null) {
            stack.push(slow);
            fast = fast.next.next;
            slow = slow.next;
            if (fast == null)
                isOdd = false;
        }
        //奇数个还需在移一步
        if (isOdd)
            slow = slow.next;
        //出栈比对
        while (!stack.isEmpty()) {
            if (stack.pop().val != slow.val)
                return false;
            slow = slow.next;
        }
        return true;
    }
}
